Zkouška Kantor 14. 1. 2025

1. [9 bodů] Kolik čísel zbyde z množiny $\{1,\dots ,1000\}$ po vyškrtání všech násobků čísel $6,7,8$?

2. (a) [2 body] Nechť $(X,\preccurlyeq )$ je nějaká částečně uspořádané množina. Doplňte definice nejmenšího prvku a minimálního prvku částečně uspořádané množiny $(X,\preccurlyeq )$:
   $x\in X$ je nejmenší prvek č.u.m. $(X,\preccurlyeq )$, pokud…
   $x\in X$ je minimální prvek č.u.m. $(X,\preccurlyeq )$, pokud…

   (b) [3 body] Nechť $W$ je množina všech přirozených čísel $n$ tvaru $n=2^a\cdot 5^b$, kde $a,b$ jsou celá čísla taková, že $a\ge 0,b\ge 0$ a $1\le a+b\le 15$. (Například $25=5\cdot 5$ a $40=5\cdot 2^3$ a $32768=2^{15}$ do množiny $W$ patří, ale $1$ do $W$ nepatří a $6=3\cdot 2$ také ne.) Kolik má množina $W$ prvků?

   (c) [3 body] Nechť $\preccurlyeq w$ značí relaci dělitelnosti na množině $W$ (definované výše), t.j. pro $x,y\in W$ máme $x\preccurlyeq wy$ právě tehdy, když $y$ je násobek čísla $x$. Napište nějaký nejdelší řetězec v množině $(W,\preccurlyeq w)$.

   (d) [4 body] Najděte nějaký netriviální dolní odhad pro velikost největšího antiřetězce (nezávislé množiny) v množině $P=(W,\preccurlyeq w)$ definované výše (t.j. nerovnost $\alpha (P)\ge \dots$). Toto můžete udělat buďto přímo, nebo třeba s použitím nějaké věty z přednášky.

3. [4+10 bodů] Formulujte a dokažte větu, která nám říká, jaký nejvyšší počet hran může mít rovinný graf na $n$ vrcholech.

4. Nechť $n$ je přirozené číslo větší než $1$. Definujeme graf $G_n$ takto:
   Jeho vrcholy jsou všechny množiny $A\subset \{1,\dots ,n\}$, pro něž platí $|A|<n$.
   Dvě z nich jsou spojeny hranou právě tehdy, když jsou disjunktní.
   Například pro $n=3$ dostaneme tento graf:

   (a) [3 body] Pro která $n$ je graf $G_n$ souvislý? Odpověď dostatečně zdůvodněte.

   (b) [4 body] Nechť $A\subset \{1,\dots ,n\}$ je množina velikosti menší než $n$. Jaký je stupeň vrcholu, který odpovídá množině $A$? (Závisí nějak na velikosti množiny $A$, na $n$, nebo případně na něčem jiném)?

   (c) [3 body] Pro která $n$ je graf $G_n$ eulerovský? Odpověď dostatečně odůvodněte.

5. (a) [2 body] Nechť $X$ je náhodná veličina na pravděpodobnostním prostoru $(\Omega ,\mathcal{P}(\Omega ),P)$. Napište vzorec pro výpočet střední hodnoty. Můžete si vybrat: buďto ten, který střední hodnotu definuje, nebo praktičtější vzorec, podle kterého se stření hodnota běžně počítá.
   $\mathbb{E}(X)=$

   (b) [3 body] Hodíme kostkou a definujeme náhodnou veličinu $X$ takto: pokud nám padla šestka, tak $X=1$, a pokud padlo jiné číslo, tak $X=0$. Spočítejte střední hodnotu náhodné veličiny $X$. Výsledek dostatečně odůvodněte, jen číslo nestačí.

   (c) [5 bodů] Nyní hodíme kostkou stokrát a označíme $Y$ počet jedniček, které nám v těch sto hodech padly (tedy $Y$ je náhodná veličina, která nabývá hodnot mezi $0$ a $100$). Spočítejte střední hodnotu náhodné veličiny $Y$. Svoje řešení dostatečně odůvodněte.

   (d) [3 body] Jaká je pravděpodobnost, že pro náhodnou veličinu $Y$ definovanou výše máme $Y=10$?